public class Solution124 {
    int res;

    public int maxPathSum(TreeNode root) {
        res = root.val;
        PathSum(root);
        return res;
    }

    public int PathSum(TreeNode root) {
        if (root.left == null && root.right == null) {
            res = Math.max(res, root.val);
            return root.val;
        }
        int ans = root.val;
        int leftSum = 0, rightSum = 0;
        if (root.left != null) {
            leftSum = PathSum(root.left);
        }
        if (root.right != null) {
            rightSum = PathSum(root.right);
        }
        int big = Math.max(leftSum, rightSum);
        int small = Math.min(leftSum, rightSum);
        if (small > 0) {
            ans += big + small;
        } else if (big > 0) {
            ans += big;
        }
        res = Math.max(res, ans);
        return root.val + Math.max(0, big);
    }
}
